Anh có trận đấu đầu tiên cho Seleção vào ngày 14 tháng 9 năm 2011,trong trận hòa không bàn thắng với đại kình địch Argentina. Bàn thắng của anh đến trong trận đấu với chính Argentina một năm sau vào ngày 20 tháng 9 năm 2012, khi anh ghi bàn gỡ hòa 1-1 rồi sau đó chiến thắng 3-1.

Cúp Liên đoàn các châu lục 2013

Anh được chọn bởi huấn luyện viên Luiz Felipe Scolari cho đội hình 23 cầu thủ Brazil tham dự Cúp Liên đoàn các châu lục 2013 diễn ra trên sân nhà. Và trong trận đấu cuối cùng của vòng loại gặp Anh trên sân Maracanã, Paulinho có cú volley sau quả tạt của Lucas Moura để cân bằng tỉ số 2–2. Trận đấu đầu tiên của vòng bảng vào ngày 15 tháng 6 với Nhật Bản, Paulinho ghi bàn thắng thứ hai của Brazil trong chiến thắng 3–0.[12] Trận bán kết với Uruguay vào ngày 26 tháng 6, Paulinho ghi bàn ấn định tỉ số ở phút thứ 86 giúp Brazil thắng 2–1 đầy nghẹt thở và tiến vào trận chung kết. Trận chung kết gặp Đội tuyển bóng đá quốc gia Tây Ban Nha, anh ghi bàn thắng thứ hai giúp Brazil đánh bại đội đương kim vô địch thế giới và châu Âu 3-0. Kết thúc giải đấu, Paulinho nhận danh hiệu quả bóng đồng, giải thưởng dành cho cầu thủ xuất sắc thứ ba giải đấu. Sau Confed Cup anh nhận được nhiều lời đề nghị từ các đội bóng lớn hàng đầu châu Âu, tuy nhiên anh quyết định chọn Tottenham Hotspur.

World Cup 2014

Anh được huấn luyện viên Luiz Felipe Scolari triệu tập vào danh sách 23 cầu thủ tham dự World Cup 2014 tổ chức tại quê nhà Brasil. Tại giải đấu này, anh không ghi được bàn thắng nào nhưng đã có những pha kiến tạo thành bàn để giúp Brasil góp mặt ở vòng bán kết sau 12 năm chờ đợi kể từ World Cup 2002. Ở vòng bán kết, vũ công Samba đã phải nhận thất bại nặng nề 1-7 trước những cỗ xe tăng Đức (đội sau đó đăng quang), đẩy Brasil xuống chơi ở trận tranh hạng ba với Hà Lan và thua chung cuộc 0-3, kết thúc giải ở vị trí thứ tư và cá nhân Paulinho không để lại ấn tượng gì.

World Cup 2018

Anh tiếp tục được huấn luyện viên Tite triệu tập tham dự World Cup 2018 trên đất Nga. Tại giải đấu này, anh chỉ có một bàn thắng trong trận thắng 2-0 trước Serbia. Đội tuyển Brasil sau đó lọt vào tứ kết và thua chung cuộc 1-2 trước Bỉ.